1. Field of the Invention
The present invention relates to a high-speed routing control system, and particularly to a high-speed routing control system for an ATM (Asynchronous Transfer Mode) connectionless communication apparatus for performing identification at IP (Internet Protocol) packets on the basis of only information of ATM layers by VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier) of the ATM layers in an ATM network, whereby transfer processing is performed with no delay of packet fabrication processing.
2. Description of the Related Art
Recently, it has been more increasingly required that the local connectionless characteristic of LAN (Local Area Network) at user sides is installed in a global ATM network to practically use the ATM network at high speed and at low price.
In the original ATM network, the connection setting is performed by signaling prior to the transfer of main signal data, and the detailed cost estimation and CAC (Connection Admission Control) calculation are performed every connection setting by each switch to select the optimum path from a plurality of candidates. At the same time, a resource to satisfy a QOS (Quality of Service) requirement from users is ensured.
In a routing protocol represented by PNNI (Private Network-to-Network Interface) and OSPF (Open Shortest Path First) in IP (Internet Protocol) communication, the "Dijkstra" algorithm is used to select the optimum path.
In the "Dijkstra" algorithm, the minimum path having the same cost is calculated on the basis of link information from all nodes to form a tree (route map: the minimum tree) extending from the root (self node) to each destination node. In order to perform the "Dijkstra" algorithm, each node is required to manage the state of links to be directly connected, that is, the topology as a path estimation and to notify the information thereof to all the nodes.
Therefore, in PNNI and OSPF, a method known as "Flooding" is defined as a method for notifying the link information. This method is used to quickly transmit a packet containing topology information into a constant area. This method has the following basic operation. That is, if the received information is newer than the information which has been owned by each node, the node distributes the new information to the others. However, if the received information is older, the node discards the information.
FIG. 2 is a conceptual diagram showing a method for distributing the topology information according to "Flooding" in PNNI. This method provides a propagation system which is characterized in that when the link status between A.1 and X.1 is varied, the node A.1 which detects the variation serves as a transmitter to advertize the information to a specific logical area PG (Peer Group: A) like "flood".
On the other hand, in a communication system of a normal connectionless network which is represented by an IP packet communication, there is no QOS request from an user, and any secondary optimizing processing to estimate a path by signaling processing is not performed at the network side. This type of connectionless communication system uses a manner of setting a direct connection path in addition to a direct connection path to enable dynamic switching operation to the bypass path in order to satisfy the communication request at maximum without discarding the packet even when the line is disconnected or one-way communication is instantaneously concentrated
As a system with a function of selecting to the bypass path, there has been proposed a method of preparing plural candidates serving as plural bypass paths and monitoring a surplus band value every candidate path to switch to a path having a larger surplus band when the connectionless communication is performed in an ATM network (for example, Japanese Laid-open Patent Application No. Hei-3-242063, etc.).
FIG. 3 is a block diagram showing a conventional connectionless processing device in an ATM network. As shown in FIG. 3, the connectionless processing device comprises a receiver 31, a target address identifying unit 32, a table storing unit 33, a transmission control unit 34 and a transmission unit 35.
FIG. 4 is a flowchart showing the operation flow of the conventional transmission control unit. According to the conventional method, as shown in FIG. 4, upon reception of a connectionless packet (S1), a destination address is extracted from additive information of the packet to select PVC (Permanent Virtual Connection) corresponding to the destination address (S2).
As bypass path setting means, the use amount of PVCs of a direct-connect path and plural bypass paths are managed in the table storing unit 33 of FIG. 3 (S4, S5), and the most empty PVC is selected as a bypass path in the transmission control unit 34, thereby satisfying a communication request from an user (S3, S6, S7, S8).
However, the conventional routing control system as described above has the following problems.
A first problem resides in that the routing processing cannot be performed at high speed. That is, since the determination of a path on the basis of a link status type path estimation which is represented by the "Dijkstra" algorithm is performed by using a broadcast type of "Flooding" as a propagation system, the traffic amount which is needed to exchange routing information is increased and thus the information exchange is not frequently performed. Accordingly, this system has a limitation in real-time processing, and the optimum performance in the routing operation is lowered.
According to the PNNI signaling method in the ATM network, as precise check means, a secondarily detailed path estimation which satisfies QOS declared by an user is performed every connection setting by CAC (Connection Admission Control) processing or crank back processing, thereby determining the routing path. However, any delay occurs due to overhead of the signaling processing.
In order to enhance the precision of the permissible band value of each path, the conventional bypass path selection method needs complicated calculations such as prediction of the traffic variation characteristic, calculation of a cost function which is faithful to the real link topology variation, etc., and thus the speed of the judgment processing as to whether the switching to the bypass path is performed cannot be increased. The problem is caused by the fact that any method is not provided with processing means which gives high priorities to high speed and low delay to derive a bypass path which is the optimum solution within a predetermined time.
A second problem resides in that the traffic amount is increased in topology information propagation. The permissible band of each path which serves as the judgment criterion of a conventional cost estimation is varied at all times with being dependent on the buffer occupation rate of each connectionless processing device, and thus the traffic characteristic. Accordingly, the routing table is renewed in accordance with the variation characteristic of the permissible band of each path, and thus the routing control in the network falls into a confused state. Further, the traffic amount to advertise the topology variation to each connectionless communication device is increased. The problem is caused by the fact that the surplus band value is reflected to the cost information and "Flooding" is used as the propagation system.
A third problem resides in that the conventional routing control system cannot follow the large-scaling of the network. The direct cause of the problem is in that the propagation system is of "Flooding" type. Representing the number of connectionless communication devices by N, the topology information propagation traffic amount is increased in the order to O(N.sup.2).
The following three points are considered as means for controlling the traffic amount.
The first means is a method of providing a timer for suppressing the traffic amount in each connectionless communication device.
The second means is a method of annihilating a packet after lapse of a predetermined time by using the lifetime of the header portion of a packet for which the exchange of the topology information is performed.
The third means is a method of dividing and hierarchizing a logical area for which "flooding" is performed to thereby restrict an advertising range, and then transmitting summary information between areas, and between an subordinate area and a superordinate area.
FIG. 2 shows the "Flooding" method in a hierarchized method, and shows that two links of A.1-X.1 link and A.2-X.2 link exist between PG(A) 202-PG(X) 203 in the subordinate layer, however, in the superordinate layer topology information (topology aggregation) in which two links are integrated into one link between A-X is subjected to "Flooding".
The excessive traffic increase phenomenon can be moderated to some degree by the above control means. However, representing the number of divided areas by m, the topology information propagation traffic amount is in the order of O(N.sup.2 /m) and thus it still trends to increase. Therefore, it is difficult to follow the large-scaling of the network. Further, when the number (m) of divided areas is increased to reduce the advertising range of the topology information, an error occurs during the integration process of the topology information, so that the accuracy of the routing is lost.